home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / mesh.bak < prev    next >
Encoding:
Text File  |  2001-01-02  |  9.4 KB  |  386 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. /*
  6. ===============================================================
  7.  
  8. MESH SUBDIVISION
  9.  
  10. ===============================================================
  11. */
  12.  
  13.  
  14. int    originalWidths[MAX_EXPANDED_AXIS];
  15. int    originalHeights[MAX_EXPANDED_AXIS];
  16.  
  17. int    neighbors[8][2] = {
  18.     {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
  19. };
  20.  
  21. void FreeMesh( mesh_t *m ) {
  22.     free( m->verts );
  23.     free( m );
  24. }
  25.  
  26. void PrintMesh( mesh_t *m ) {
  27.     int        i, j;
  28.  
  29.     for ( i = 0 ; i < m->height ; i++ ) {
  30.         for ( j = 0 ; j < m->width ; j++ ) {
  31.             printf("(%5.2f %5.2f %5.2f) "
  32.                 , m->verts[i*m->width+j].xyz[0]
  33.                 , m->verts[i*m->width+j].xyz[1]
  34.                 , m->verts[i*m->width+j].xyz[2] );
  35.         }
  36.         printf("\n");
  37.     }
  38. }
  39.  
  40.  
  41. /*
  42. =================
  43. TransposeMesh
  44.  
  45. Returns a transposed copy of the mesh, freeing the original
  46. =================
  47. */
  48. mesh_t *TransposeMesh( mesh_t *in ) {
  49.     int            w, h;
  50.     mesh_t        *out;
  51.  
  52.     out = malloc( sizeof( *out ) );
  53.     out->width = in->height;
  54.     out->height = in->width;
  55.     out->verts = malloc( out->width * out->height * sizeof( drawVert_t ) );
  56.  
  57.     for ( h = 0 ; h < in->height ; h++ ) {
  58.         for ( w = 0 ; w < in->width ; w++ ) {
  59.             out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
  60.         }
  61.     }
  62.  
  63.     FreeMesh( in );
  64.  
  65.     return out;
  66. }
  67.  
  68. void InvertMesh( mesh_t *in ) {
  69.     int            w, h;
  70.     drawVert_t    temp;
  71.  
  72.     for ( h = 0 ; h < in->height ; h++ ) {
  73.         for ( w = 0 ; w < in->width / 2 ; w++ ) {
  74.             temp = in->verts[ h * in->width + w ];
  75.             in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
  76.             in->verts[ h * in->width + in->width - 1 - w ] = temp;
  77.         }
  78.     }
  79. }
  80.  
  81. /*
  82. =================
  83. MakeMeshNormals
  84.  
  85. =================
  86. */
  87. void MakeMeshNormals( mesh_t in ) {
  88.     int        i, j, k, dist;
  89.     vec3_t    normal;
  90.     vec3_t    sum;
  91.     int        count;
  92.     vec3_t    base;
  93.     vec3_t    delta;
  94.     int        x, y;
  95.     drawVert_t    *dv;
  96.     vec3_t        around[8], temp;
  97.     qboolean    good[8];
  98.     qboolean    wrapWidth, wrapHeight;
  99.     float        len;
  100.  
  101.     wrapWidth = false;
  102.     for ( i = 0 ; i < in.height ; i++ ) {
  103.         VectorSubtract( in.verts[i*in.width].xyz, 
  104.             in.verts[i*in.width+in.width-1].xyz, delta );
  105.         len = VectorLength( delta );
  106.         if ( len > 1.0 ) {
  107.             break;
  108.         }
  109.     }
  110.     if ( i == in.height ) {
  111.         wrapWidth = true;
  112.     }
  113.  
  114.     wrapHeight = false;
  115.     for ( i = 0 ; i < in.width ; i++ ) {
  116.         VectorSubtract( in.verts[i].xyz, 
  117.             in.verts[i + (in.height-1)*in.width].xyz, delta );
  118.         len = VectorLength( delta );
  119.         if ( len > 1.0 ) {
  120.             break;
  121.         }
  122.     }
  123.     if ( i == in.width) {
  124.         wrapHeight = true;
  125.     }
  126.  
  127.  
  128.     for ( i = 0 ; i < in.width ; i++ ) {
  129.         for ( j = 0 ; j < in.height ; j++ ) {
  130.             count = 0;
  131.             dv = &in.verts[j*in.width+i];
  132.             VectorCopy( dv->xyz, base );
  133.             for ( k = 0 ; k < 8 ; k++ ) {
  134.                 VectorClear( around[k] );
  135.                 good[k] = false;
  136.  
  137.                 for ( dist = 1 ; dist <= 3 ; dist++ ) {
  138.                     x = i + neighbors[k][0] * dist;
  139.                     y = j + neighbors[k][1] * dist;
  140.                     if ( wrapWidth ) {
  141.                         if ( x < 0 ) {
  142.                             x = in.width - 1 + x;
  143.                         } else if ( x >= in.width ) {
  144.                             x = 1 + x - in.width;
  145.                         }
  146.                     }
  147.                     if ( wrapHeight ) {
  148.                         if ( y < 0 ) {
  149.                             y = in.height - 1 + y;
  150.                         } else if ( y >= in.height ) {
  151.                             y = 1 + y - in.height;
  152.                         }
  153.                     }
  154.  
  155.                     if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
  156.                         break;                    // edge of patch
  157.                     }
  158.                     VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
  159.                     if ( VectorNormalize( temp, temp ) == 0 ) {
  160.                         continue;                // degenerate edge, get more dist
  161.                     } else {
  162.                         good[k] = true;
  163.                         VectorCopy( temp, around[k] );
  164.                         break;                    // good edge
  165.                     }
  166.                 }
  167.             }
  168.  
  169.             VectorClear( sum );
  170.             for ( k = 0 ; k < 8 ; k++ ) {
  171.                 if ( !good[k] || !good[(k+1)&7] ) {
  172.                     continue;    // didn't get two points
  173.                 }
  174.                 CrossProduct( around[(k+1)&7], around[k], normal );
  175.                 if ( VectorNormalize( normal, normal ) == 0 ) {
  176.                     continue;
  177.                 }
  178.                 VectorAdd( normal, sum, sum );
  179.                 count++;
  180.             }
  181.             if ( count == 0 ) {
  182. //printf("bad normal\n");
  183.                 count = 1;
  184.             }
  185.             VectorNormalize( sum, dv->normal );
  186.         }
  187.     }
  188. }
  189.  
  190. /*
  191. =================
  192. PutMeshOnCurve
  193.  
  194. Drops the aproximating points onto the curve
  195. =================
  196. */
  197. void PutMeshOnCurve( mesh_t in ) {
  198.     int        i, j, l;
  199.     float    prev, next;
  200.  
  201.     // put all the aproximating points on the curve
  202.     for ( i = 0 ; i < in.width ; i++ ) {
  203.         for ( j = 1 ; j < in.height ; j += 2 ) {
  204.             for ( l = 0 ; l < 3 ; l++ ) {
  205.                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
  206.                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
  207.                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
  208.             }
  209.         }
  210.     }
  211.  
  212.     for ( j = 0 ; j < in.height ; j++ ) {
  213.         for ( i = 1 ; i < in.width ; i += 2 ) {
  214.             for ( l = 0 ; l < 3 ; l++ ) {
  215.                 prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
  216.                 next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
  217.                 in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
  218.             }
  219.         }
  220.     }
  221. }
  222.  
  223.  
  224. /*
  225. =================
  226. SubdivideMesh
  227.  
  228. =================
  229. */
  230. mesh_t SubdivideMesh( mesh_t in, float maxError, float minLength ) {
  231.     int            i, j, k, l;
  232.     vec_t        prev[10], next[10], mid[10], delta[10];
  233.     float        len;
  234.     mesh_t        out;
  235.     vec_t        expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS][10];
  236.  
  237.     out.width = in.width;
  238.     out.height = in.height;
  239.  
  240.     for ( i = 0 ; i < in.height ; i++ ) {
  241.         memcpy( expand[i], &in.verts[i*in.width], in.width*sizeof(drawVert_t) );
  242.     }
  243.  
  244.     for ( i = 0 ; i < in.height ; i++ ) {
  245.         originalHeights[i] = i;
  246.     }
  247.     for ( i = 0 ; i < in.width ; i++ ) {
  248.         originalWidths[i] = i;
  249.     }
  250.  
  251.     // horizontal subdivisions
  252.     for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
  253.         // check subdivided midpoints against control points
  254.         for ( i = 0 ; i < out.height ; i++ ) {
  255.             for ( l = 0 ; l < 3 ; l++ ) {
  256.                 prev[l] = expand[i][j+1][l] - expand[i][j][l]; 
  257.                 next[l] = expand[i][j+2][l] - expand[i][j+1][l]; 
  258.                 mid[l] = (expand[i][j][l] + expand[i][j+1][l] * 2
  259.                         + expand[i][j+2][l] ) * 0.25;
  260.             }
  261.  
  262.             // if the span length is too long, force a subdivision
  263.             if ( VectorLength( prev ) > minLength 
  264.                 || VectorLength( next ) > minLength ) {
  265.                 break;
  266.             }
  267.  
  268.             // see if this midpoint is off far enough to subdivide
  269.             VectorSubtract( expand[i][j+1], mid, delta );
  270.             len = VectorLength( delta );
  271.             if ( len > maxError ) {
  272.                 break;
  273.             }
  274.         }
  275.  
  276.         if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
  277.             break;    // can't subdivide any more
  278.         }
  279.  
  280.         if ( i == out.height ) {
  281.             continue;    // didn't need subdivision
  282.         }
  283.  
  284.         // insert two columns and replace the peak
  285.         out.width += 2;
  286.  
  287.         for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
  288.             originalWidths[k] = originalWidths[k-2];
  289.         }
  290.         originalWidths[j+3] = originalWidths[j+1];
  291.         originalWidths[j+2] = originalWidths[j+1];
  292.         originalWidths[j+1] = originalWidths[j];
  293.  
  294.         for ( i = 0 ; i < out.height ; i++ ) {
  295.             for ( l = 0 ; l < 10 ; l++ ) {
  296.                 prev[l] = ( expand[i][j][l] + expand[i][j+1][l] ) * 0.5;
  297.                 next[l] = ( expand[i][j+1][l] + expand[i][j+2][l] ) * 0.5;
  298.                 mid[l] = ( prev[l] + next[l] ) * 0.5;
  299.             }
  300.  
  301.             for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
  302.                 Vec10Copy( expand[i][k-2], expand[i][k] );
  303.             }
  304.             Vec10Copy( prev, expand[i][j + 1] );
  305.             Vec10Copy( mid,  expand[i][j + 2] );
  306.             Vec10Copy( next, expand[i][j + 3] );
  307.         }
  308.  
  309.         // back up and recheck this set again, it may need more subdivision
  310.         j -= 2;
  311.  
  312.     }
  313.  
  314.     // vertical subdivisions
  315.     for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
  316.         // check subdivided midpoints against control points
  317.         for ( i = 0 ; i < out.width ; i++ ) {
  318.             for ( l = 0 ; l < 3 ; l++ ) {
  319.                 prev[l] = expand[j+1][i][l] - expand[j][i][l]; 
  320.                 next[l] = expand[j+2][i][l] - expand[j+1][i][l]; 
  321.                 mid[l] = (expand[j][i][l] + expand[j+1][i][l] * 2
  322.                         + expand[j+2][i][l] ) * 0.25;
  323.             }
  324.  
  325.             // if the span length is too long, force a subdivision
  326.             if ( VectorLength( prev ) > minLength 
  327.                 || VectorLength( next ) > minLength ) {
  328.                 break;
  329.             }
  330.             // see if this midpoint is off far enough to subdivide
  331.             VectorSubtract( expand[j+1][i], mid, delta );
  332.             len = VectorLength( delta );
  333.             if ( len > maxError ) {
  334.                 break;
  335.             }
  336.         }
  337.  
  338.         if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
  339.             break;    // can't subdivide any more
  340.         }
  341.  
  342.         if ( i == out.width ) {
  343.             continue;    // didn't need subdivision
  344.         }
  345.  
  346.         // insert two columns and replace the peak
  347.         out.height += 2;
  348.  
  349.         for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
  350.             originalHeights[k] = originalHeights[k-2];
  351.         }
  352.         originalHeights[j+3] = originalHeights[j+1];
  353.         originalHeights[j+2] = originalHeights[j+1];
  354.         originalHeights[j+1] = originalHeights[j];
  355.  
  356.         for ( i = 0 ; i < out.width ; i++ ) {
  357.             for ( l = 0 ; l < 10 ; l++ ) {
  358.                 prev[l] = ( expand[j][i][l] + expand[j+1][i][l] ) * 0.5;
  359.                 next[l] = ( expand[j+1][i][l] + expand[j+2][i][l] ) * 0.5;
  360.                 mid[l] = ( prev[l] + next[l] ) * 0.5;
  361.             }
  362.  
  363.             for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
  364.                 Vec10Copy( expand[k-2][i], expand[k][i] );
  365.             }
  366.             Vec10Copy( prev, expand[j + 1][i] );
  367.             Vec10Copy( mid,  expand[j + 2][i] );
  368.             Vec10Copy( next, expand[j + 3][i] );
  369.         }
  370.  
  371.         // back up and recheck this set again, it may need more subdivision
  372.         j -= 2;
  373.  
  374.     }
  375.  
  376.     // collapse the verts
  377.  
  378.     out.verts = (drawVert_t *)expand[0];
  379.     for ( i = 1 ; i < out.height ; i++ ) {
  380.         memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
  381.     }
  382.  
  383.     return out;
  384. }
  385.  
  386.